package binaryTree;

class Node1 {

    public int val;
    public Node1 left;
    public Node1 right;
    public Node1 next;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }
    public Node1(int _val, Node1 _left, Node1 _right, Node1 _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
public class Class116 {

    public Node1 connect(Node1 root) {

//        if (root=null||root.left==null){
//            return   ;
//        }
//
//        root.left.next=root.right;
//        connect(root.left);
//        connect(root.right);
        if (root==null) return null;
        traverse(root.left,root.right);
        return  root;
    }
    void  traverse(Node1 node1,Node1 node2){
        if (node1==null||node2==null){
            return;
        }
        node1.next=node2;
        traverse(node1.left,node1.right);
        traverse(node2.left,node2.right);
        traverse(node1.right,node2.left);

    }
}
